8、Ramsey 定理

Ramsey 数

事实：六人派对

设一个派对有六个人，则其中要么有三人互相认识，要么有三人互相不认识。

证明： 考虑一个图 $G$ ， $V (G) = [6]$ 。考虑顶点 $1$ 。不妨设 $1$ 与三个顶点相连（否则考虑补图），如 $2, 3, 4$ 。若 $23, 24, 34$ 之一相邻，则存在三角形；若均不相邻，则这三个点的补图存在三角形。

定义：边染色

一个 $r -$ 边染色是一个 $f : E (K_{n}) \to {1, 2, \dots, r}$ .

定义： Ramsey 数

对 $k, l$ ，Ramsey 数 $R (k, l)$ 定义为最小的 $N$ ，使得 $K_{N}$ 任意一个 2-染色中要么有一个蓝色 $K_{k}$ ，要么有一个红色 $K_{l}$ 。

深入理解：

若 $R (k, l) \leq L$ ，则 $K_{L}$ 的任一个2-边染色要么有蓝 $K_{k}$ ，要么有红 $K_{l}$ ；
若 $R (k, l) > M$ ，则存在一种2-边染色，既无蓝 $K_{k}$ 也无红 $K_{l}$ 。

事实

$R (k, l) = R (l, k)$ 。
$R (2, l) = l$ ， $R (k, 2) = k$ 。
$R (3, 3) = 6$

证明： 1 是显然的。对2，注意到 $K_{l - 1}$ 可以全涂红，此时既无2蓝边又无 $l$ 红边。另一方面，显然 $K_{l}$ 是对的。对3，只需证 $K_{5}$ 不成立：将外部五边形涂红，内部五角星涂蓝即可。

定理：Ramsey 数的加法估计

$R (k, l) \leq R (k - 1, l) + R (k, l - 1) .$

证明： 设 $n = R (k - 1, l) + R (k, l - 1)$ 。对任意2-边染色 $G = K_{n}$ ，对任意 $x$ ，定义 $A = {y \in V (G) ∖ {x} : x y 为蓝色}$ 及 $B = {y \in V (G) ∖ {x} : x y 为红色}$ 。则

| A | + | B | = n - 1 = R (k - 1, l) + R (k, l - 1) - 1.

由抽屉原理，要么 $| A | \geq R (k - 1, l)$ ，要么 $| B | \geq R (k, l - 1)$ 。注意 $K_{n}$ 的诱导子图都是完全图，故 $G [A]$ 和 $G [B]$ 之一中有 $R (k - 1, l)$ 或 $R (k, l - 1)$ ，则 $G [A \cup {x}]$ 或 $G [B \cup {y}]$ 中有一个要么包含 $K_{k}$ 红，要么包含 $K_{l}$ 蓝。

定理（Ramsey）

$R (k, l)$ 有限。具体来说，

R (k, l) \leq (\binom{k + l - 2}{k - 1}) .

证明： 归纳法。基础为 $R (2, l) = R (l, 2) = l$ 。设 $R (s, t)$ 满足条件对任意 $s + t < k + l$ ，则

R (k, l) \leq R (k - 1, l) + R (k, l - 1) \leq (\binom{k - 1 + l - 2}{k - 2}) + (\binom{k + l - 1 - 2}{k - 1}) = (\binom{k + l - 2}{k - 1}) .

练习

用 Ramsey 定理证明：对任意 $k \geq 2$ ，都存在正整数 $n$ 使得任意 $n$ 个不同实数的序列都有一个 $k$ 长度单调子序列．

证明： 令 $n = R (k, k)$ ，对任一序列 $a_{1}, \dots, a_{n}$ ，构造完全图 $K_{n}$ ：顶点集为 $a_{1}, \dots, a_{n}$ ，且对 $1 \leq i < j \leq n$ ，边 $a_{i} a_{j}$ 染红，若 $a_{i} < a_{j}$ ；染蓝，若相反．由 Ramsey 定理，存在一个单色 $K_{k}$ ——这给出一个单调链．

定理：加强

若对某个 $(k, l)$ ， $R (k - 1, l)$ 与 $R (k, l - 1)$ 均为偶数，则

R (k, l) \leq R (k - 1, l) + R (k, l - 1) - 1.

证明： 设 $n = R (k - 1, l) + R (k, l - 1) - 1$ ，则 $n$ 为奇。考虑 $K_{n}$ 的一个 $2 -$ 边染色。对任意顶点 $x$ ，同上定义 $A_{x}$ 与 $B_{x}$ 集。先前的证明告诉我们 $| A_{x} | \geq R (k - 1, l)$ 或 $| B_{x} | \geq R (k, l - 1)$ 时可以找到蓝 $K_{k}$ 或红 $K_{l}$ 。若设 $| A_{x} | \leq R (k - 1, l) - 1$ 且 $| B_{x} | \leq R (k, l - 1) - 1$ 对任意顶点 $v$ ，则

n = A_{x} + B_{x} - 1 \leq R (k - 1, l) + R (k, l - 1) - 1.

这说明对任意 $x$ ， $| A_{x} | = R (k - 1, l) - 1$ 且 $| B_{x} | = R (k, l - 1) - 1$ 。现在考虑由蓝边组成的图 $G$ 。注意 $G$ 有奇数个顶点且任意顶点都有奇数度数，矛盾！

推论

$R (3, 4) = 9$ 。

证明： $R (2, 4) = 4$ ， $R (3, 3) = 6$ ，于是

R (3, 4) \leq R (2, 4) + R (3, 3) - 1 = 9.

$K_{8}$ 的一个反例是：用红色染 $K_{8}$ 的外圈及四条直径。

已知的几个例子是： $K (4, 4) = 18$ ， $K (4, 5) = 25$ ，且 $K (5, 5)$ 在 $43$ 和 $46$ 之间。

定义：多重 Ramsey 数

对 $k \geq 2$ 、整数 $s_{1}, \dots, s_{k} \geq 2$ ，Ramsey 数 $R_{k} (s_{1}, \dots, s_{k})$ 是最小的正整数 $N$ ，使得任何一个 $k -$ 染色都有一个 $K_{s_{i}}$ 团。

练习

证明：

R_{k} (s_{1}, \dots, s_{k}) < \infty .

证明： $n = 2$ 已证。设命题对 $k - 1$ 成立，令 $n = R_{k - 1} (s_{1}, \dots, s_{k - 2}, R_{2} (s_{k - 1}, s_{k}))$ ，由归纳假设知 $n < \infty$ ．对 $K_{n}$ 的一个 $k -$ 染色，我们把第 $k$ 色改为 $k - 1$ 色．若存在单色 $K_{s_{i}}$ ， $1 \leq i \leq k - 2$ ，已证．若不存在，则存在一个 $K_{R_{2} (s_{k - 1}, s_{k - 1})}$ ，其中有颜色 $k - 1$ ．回到原图中，这个子图中要么有一个 $k - 1$ 色 $K_{s_{k - 1}}$ ，要么有一个 $k$ 色 $K_{s_{k}}$ ，于是

R_{k} (s_{1}, \dots, s_{k}) \leq R_{k - 1} (s_{1}, s_{2}, \dots, R_{2} (s_{k - 1}, s_{k})) < \infty .

综上，证毕．

练习

证明

2^{k} \leq R_{k} (3, 3, \dots, 3) \leq (k + 1)! .

证明： 先证左端．归纳法． $k = 2$ 时显然．假设命题对 $k$ 成立，我们证明命题对 $k + 1$ 成立．由归纳假设，存在 $k -$ 边染色 $K_{2^{k}}$ ，使得不存在单色三角形．令 $K_{2^{k}}^{'}$ 是 $K_{2^{k}}$ 的一个拷贝．对任意 $a \in K_{2^{k}}$ ， $b \in K_{2^{k}}^{'}$ ，把 $a b$ 之间连一根 $k + 1$ 染色的线．这就得到了一个 $k + 1$ 染色的 $K_{2^{k + 1}}$ 图．从而 $R_{k} (3, 3, \dots, 3) \geq 2^{k}$ ．

再证右端．同样用归纳法． $k = 2$ 时显然．设命题对 $k$ 成立，则对 $k + 1$ ，令 $n_{k} = (k + 1) R_{k} (3, 3, \dots, 3) + 1$ ．我们证明

R_{k + 1} (3, \dots, 3) \leq n_{k}, \forall k \geq 1.

事实上，考虑 $K_{n_{k}}$ 的 $k + 1$ 染色．固定一个顶点 $v \in K_{n_{k}}$ ．由于 $v$ 与 $n_{k} - 1$ 条边相关联，存在一个颜色 $i$ 使得

\frac{n_{k} - 1}{k + 1} = R_{k} (3, 3, \dots, 3)

条边染色 $i$ ．考虑子图 $H$ 由顶点 $u$ 诱导，使得 $u v$ 有颜色 $i$ ．如果 $H$ 中存在一条有颜色 $i$ 的边，则其中有 $i$ 三角；否则 $H$ 由 $k$ 种颜色染成，由于其中至少有 $R_{k} (3, \dots, 3)$ 个点，因此 $H$ 中存在一个单色三角形．综上无论如何图中都有一个单色三角形，此时

R_{k + 1} (3, \dots, 3) \leq (k + 1) \cdot (k + 1)! + 1 = (k + 2)! .

证毕．

定理（Schur）

对 $k \geq 2$ ，存在整数 $N = N (k)$ 使得对任意染色 $φ : [N] \to [k]$ ，存在整数 $x, y, z \in [N]$ 使 $φ (x) = φ (y) = φ (z)$ 且 $x + y = z$ 。

证明： 令 $N = R_{k} (3, 3, \dots, 3)$ 。定义 $k -$ 边染色 $i j \mapsto φ (| i - j |)$ 。则存在单色三角形 $i j l$ ，则 $φ (l - j) = φ (l - i) = φ (j - i)$ 。令 $x = l - j, y = j - i, z = l - i$ 即证。

定理（Schur）

对任意 $m \geq 1$ ，存在整数 $p (m)$ 使得对任意 $p \geq p (m)$ ， $x^{m} + y^{m} = z^{m} \mod p$ 有解。

证明： 考虑 $Z_{p}^{*}$ 的生成元 $g$ ，定义染色 $φ : Z_{p}^{*} \to {0, 1, \dots, m - 1}$ , $g^{i m + j} \mapsto j$ ，这里 $0 \leq j \leq 1$ 且 $0 \leq i m + j \leq p - 2$ 。取上面的定理中给出的 $N (m)$ 为 $p (m)$ ，则由题知存在 $x, y, z \in Z_{p}^{*}$ 使得 $x + y = z$ 且 $φ (x) = φ (y) = φ (z)$ ，于是

g^{i_{1} m + j} + g^{i_{2} m + j} = g^{i_{3} m + j} \mod p .

即证。

集合上 Ramsey 定理

现在，考虑 $[n]$ 的 $k$ 元子集上的染色。图 Ramsey 定理对 $k = 2$ 时有说法。

定理

对任意自然数 $1 \leq k \leq s$ 及 $r \geq 2$ ，存在自然数 $n = R_{r} (k; s)$ 使得对任意 $[n]$ 的 $k -$ 子集都被染为 $r$ 种颜色，都存在一个 $[n]$ 的 $s$ 子集，使得所有 $k -$ 子集都有同一颜色。

为了证明，我们首先观察到只需研究 $r = 2$ 时即可。

引理：被2控制

$R_{r + 1} (k; s) \leq R_{r} (k; R_{2} (k; s)) .$

证明： 令 $N = R_{r} (k; R_{2} (k; s))$ 。设 $N$ 元集对其 $k$ 子集的一种 $r + 1$ 染色 $0, 1, \dots, r$ 给定。将其考虑为这种 $r -$ 染色： $0, 1$ 对应同一种。由 $N$ 的选法，要么存在一个 $R_{2} (k; s)$ 元子集，其中颜色由 $2, \dots, r$ 给出（则已证），要么存在一个 $R_{2} (k; s)$ 元子集 $Y$ ，其中染色均为 $0$ 或 $1$ 。由 $Y$ 的大小，其一些 $s -$ 元子集的各 $k -$ 元集必是单色的。

定理的证明： 为了更方便证明，我们定义一种更精细版本的 Ramsey 数。令 $R (k; s, t)$ 满足如下条件：如果一个 $n$ 元集的 $k -$ 子集被两种颜色 $0, 1$ 染色，则要么某些 $s$ 子集的全体 $k$ 子集染 $0$ ，要么某些 $t$ 子集的全体 $k$ 元集染 $1$ 。则只需证 $R (k; s, s)$ 存在，对任意 $s \geq k$ 。我们证明：

R (k; s, t) \leq n := R (k - 1; R (k; s - 1, t), R (k; s, t - 1)) + 1.

对 $k, s, t$ 归纳。注意到由抽屉原理， $R (1; s, t) = s + t - 1$ ；且 $R (k; x, k) = R (k; k, x) = x$ ，对任意 $k$ 及 $x \geq k$ 。由归纳假设，设 $R (k; s - 1, t)$ 与 $R (k; s, t - 1)$ 均存在，并取任一 $n$ 元集 $X$ ， $n$ 如上定义。

令 $χ$ 为 $X$ 的 $k$ 元子集的一个 2-染色。固定一个点 $x \in X$ 并令 $X^{'} = X ∖ {x}$ 。定义 $X^{'}$ 上的一个新的 $k - 1$ 元染色为

χ^{'} (A) = χ (A \cup {x}) .

由对称性，可设找到了一个子集 $Y \subset X^{'}$ ，使得 $| Y | = R (k; s - 1, t)$ 且

χ^{'} (A) = 0, \forall k - 1 元集 A \subset Y .

现在，考虑 $χ$ 如何作用于 $Y$ 。由 $Y$ 的大小，其必要么有一个 $t$ 元子集，其 $k$ 子集被染为颜色 1 （证毕）或包含一个 $s - 1$ 元集 $Z$ ，其 $k -$ 子集被染为 0。对后者，考虑 $s$ 元子集 $Z \cup {x}$ 的一个 $k$ 子集 $B$ 。若 $x \notin B$ ，则 $B$ 为 $Z$ 的 $k$ 子集，故 $χ (B) = 0$ 。若 $x \in B$ ，则 $χ (B) = χ (A \cup {x}) = χ^{'} (A) = 0$ 。证毕。

一个最古老但最高人气的应用是

定理（Erdos-Szekeres）

令 $m \geq 3$ 为正整数。则存在一个正整数 $n$ ，使得平面内任意满足三点不共线的 $n$ 点集，包含 $m$ 个点构成一个凸 $m$ 边形。

证明： 令 $n = R_{2} (3; m)$ 。令 $A$ 为题中所示的图形。对任意 $a, b, c \in A$ ，令 $| a b c |$ 为 $A$ 中位于三角形 $a b c$ 内的点数。

对点三元组，定义一个2-染色 $χ$ ： $χ (a, b, c) = 0$ 若 $| a b c |$ 偶，反之为 1。由 $n$ 的选择，存在一个 $m$ 元子集 $B \subset A$ 使得其任意 $3 -$ 元子集得到同样的染色。则 $B$ 的点构成一个凸多边形：否则存在四点 $a, b, c, d$ 使得 $d$ 位于三角形 $a b c$ 中。由于任意三点不共线，我们有

| a b c | = | a b d | + | a c d | + | b c d | + 1.

但 $χ$ 作用在各三点组上为常数，矛盾！